package leecode.array.子串与子序列问题;

/**
 * @author wangxi created on 2021/3/16 23:33
 * @version v1.0
 *
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/
 *
 *  最长递增子序列
 */
public class LongestIncreasingSubsequence {

    public static void main(String[] args) {
        LongestIncreasingSubsequence obj = new LongestIncreasingSubsequence();
//        int[] nums = {10,9,2,5,3,7,101,18};
        int[] nums = {1,2};

        int i = obj.lengthOfLIS(nums);

        System.out.println(i);

        System.out.println('A' - '0');
    }

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return 0;
        }
        // 表示i下标的最大升序长度
        int[] dp = new int[nums.length];
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 可能最大的dp对应的元素并不小于nums[i]，因此需要这个判断
            //  比如：[1,3,6,7,9,4,10,5,6]
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
